Теорема о числе маршрутов в мультиорграфе

Пусть $G$ - (мульти)(ор)граф. Тогда число маршрутов длины $d$ из вершины $v_{i}$ в вершину $v_{j}$ равно: $$W(v_i, v_j, d) = M_G^d[i,j]$$

Доказательство индукцией по $d$. **База:** $d = 1$ $(v_i, v_j)$-маршруты длины 1 — это ребра $(v_i, v_j)$, а $M_G[i,j]$ — их число. **Шаг:** Любой $(v_i, v_j)$-маршрут длины $d+1$ состоит из $(v_i, v_k)$-маршрута длины $d$ и последнего ребра $(v_k, v_j)$. Значит, чтобы найти искомое число, надо перемножить количество $(v_{i}, v_{k})$-маршрутов на количество рёбер $(v_{k}, v_{j})$ и просуммировать по $k = 1, \dots, n = |V|$ 1. $W(v_i, v_k, d) = M_G^d[i,k]$ по предположению индукции. 2. $W(v_k, v_j, 1) = M_G[k,j]$ по базе индукции. 3. по определению умножения матриц $\sum\limits_{k=1}^n M_G^d[i,k] \cdot M_G[k,j] = M_G^{d+1}[i,j]$. $\square$